The present invention relates to a method and a tool for producing a telecommunication network.
A telecommunication network suitable for providing telecommunication services over a large geographical area, comprises a plurality of nodes distributed over the area to be serviced. Between some of these nodes links are provided enabling the network to establish connections between the nodes of the network such that every subscriber connected to any given node of the network can reach every other subscriber connected to any other node of the network via such links between adjacent nodes. The term xe2x80x9clinkxe2x80x9d refers to a physical connection between a pair of nodes which connection does not include any other node.
In order to ensure that the network meets the service demands, it is feasible to provide an individual link between each pair of nodes of the network. If the number of nodes of the network is N, the total number of links between nodes will then be N(Nxe2x88x921)/2. While this solution allows that two subscribers communicate with each other without involving any other nodes than the nodes immediately interfacing to the two subscribers, a network with a larger number of nodes would require an excessively high number of links, resulting in enormous costs for the implementation of the network.
Therefore, networks with a large number of nodes allow that communication paths are established between pairs of nodes, the paths consisting of a plurality of links between a corresponding plurality of pairs of nodes, such that a communication between a first node and a second node is handled by all other nodes along the path. That is, a path consists of one or more links connected in series. As an immediate consequence of this architecture, links connecting pairs of nodes will generally have to bear not only the traffic originating from the subscribers connected to the nodes connected by the link, but also traffic originating from subscribers connected to nodes connected via a path using this link. Accordingly, while in this network the total number of links is smaller than in the case that an individual link is provided between each pair of nodes, i.e. the fully connected case, the traffic capacity of the implemented links will possibly have to be higher than in the fully connected case.
Moreover, a telecommunication network usually has to after a high degree of reliability. In order to make sure that communication is possible between every pair of nodes even in case that a given number of links or nodes fail to operate, there may exist the requirement that every pair of nodes of the network is connected with each other via not less than a given number of disjoint paths which is by one higher than the given number of links or nodes which may fail without affecting the proper operation of the network. Here, a plurality of paths connecting the same pair of nodes is called disjoint if each link of the plurality of paths is not used by any other of these paths. A plurality of paths connecting the same pair of nodes is called node-disjoint if each node along each path is not used by any other of these paths.
The physical effort necessary for implementing a link between two nodes depends on geographical conditions and on the traffic capacity to be handled by the link. A measure for the effort required for implementing a link are the link implementation costs. As a generalization, the link implementation costs are a link attribute indicating how much physical effort is required for implementing the respective link.
It is the object of the present invention, to provide a method and a tool of producing a telecommunication network with low implementation costs in the above sense, the network satisfying the traffic demand between all pairs of nodes of the network.
According to the present invention, this object is solved as defined in claim 1 and 14, respectively. Advantageous embodiments of the present invention are given in the dependent claims.
The present invention takes into account that in terms of the link implementation costs discussed above, the most expensive part of a link is the physical action of laying cable from one node to the other. In comparison with this part of the implementation costs, the part of the implementation costs for providing a required transmission capacity is significantly smaller. The method according to the present invention takes this into account by means of selecting a path with the least implementation costs at first between less remote node pairs with a higher traffic demand and then between more distant node pairs with a higher traffic demand. In this way, the paths between nodes with small distance and high traffic demand are optimized with emphasise on the part of the implementation costs due to the geographical conditions. Moreover, when a new path has to be selected for implementation between a given pair of nodes, according to the invention the path selection takes into account the links already selected for implementation in a previous step, in order to save portions of the link implementation costs resulting from the necessity to prepare for the laying of cables. The present invention exploits the fact that once such preparations have been taken, substantially no additional effort of this kind is required for increasing the traffic capacity of the link. Accordingly, the present invention provides a method of producing a telecommunication network with a low implementation costs, given the nodes of the network, their geographical location and the traffic capacity demand between each pair of nodes of the network.
The term xe2x80x9cequivalent distancexe2x80x9d or xe2x80x9cequivalent lengthxe2x80x9d takes into account that the decision whether one link with a given traffic capacity is easier to implement than another link with the same traffic capacity, not only depends on the distance between the nodes but also on the geographical conditions along the link. As an example, the equivalent distance between two nodes linked by a buried link, is larger than the equivalent distance between two nodes at the same given distance which can be linked via a microwave link. Similarly, the equivalent length of a buried link is larger than for a link through a tunnel or the like already available. As a simple but less preferable approximation for the equivalent distance between two nodes, their geographical distance can be taken. In the same way, the equivalent length of a link or a path can be approximated by the physical length.
A preferred embodiment of the method of producing a telecommunication network according to the present invention guarantees that the implementation costs for the whole network, i.e. the sum of all link implementation costs is low and that at the same time each pair of nodes is connected via a gotten number of disjoint paths predetermined in accordance with the reliability requirements of the network.
According to a preferred embodiment of the present invention, the influence of the traffic capacity demand on the selection of the path is reduced the larger the number of paths becomes which are already selected for implementation. According to this embodiment, for a larger influence of the traffic capacity demand on the selection of paths for implementation, mainly the links already existing will be used to built new paths. If the influence of the traffic capacity demand is reduced shorter paths will be selected for implementation and more new links will be selected for implementation.
According to an embodiment of the present invention, the overall implementation costs are further optimized by means of trying to do without links selected for implementation for which the ratio between its effective link length to its physical length and to its traffic capacity is very high. This optimization is achieved by means of calculating the overall network implementation costs for the case that this particular link is not available and that instead, additional paths have been implemented for satisfying the traffic capacity demand and the reliability requirements of the network, and depending on the comparison of the overall implementation costs with the implementation costs of the network having the particular link implemented, either selecting the additional paths for implementation or maintaining the selection of the particular link for implementation.